摘要 :
Some multitrees with internal storage data structure are presented for the storage of graphical objects in CAD systems. Memory requirements are as low as those for the very compact quad trees without bisector lists (QWBL). Moreove...
展开
Some multitrees with internal storage data structure are presented for the storage of graphical objects in CAD systems. Memory requirements are as low as those for the very compact quad trees without bisector lists (QWBL). Moreover, multitrees with internal storage (MTIS) are as fast as quad list quad trees (QLQT) for region search operations.
收起
摘要 :
We consider succinct representations of labeled ordinal trees that support a rich set of operations. Our new representations support a much broader collection of operations than previous work. In our approach, labels of nodes are ...
展开
We consider succinct representations of labeled ordinal trees that support a rich set of operations. Our new representations support a much broader collection of operations than previous work. In our approach, labels of nodes are stored in a preorder label sequence, which can be compressed using any succinct representation of strings that supports access, rank and select operations. Thus, we present a framework for succinct representations of labeled ordinal trees that is able to handle large alphabets. This answers an open problem presented by Geary et al., which asks for representations of labeled ordinal trees that remain space-efficient for large alphabets. We further extend our work and present the first succinct representations for dynamic labeled ordinal trees that support several label-based operations including finding the level ancestor with a given label.
收起
摘要 :
A new form of optimality for comparison-based static dictionaries is introduced. This type of optimality, key-independent optimality, is motivated by applications that assign key values randomly. It is shown that any data structur...
展开
A new form of optimality for comparison-based static dictionaries is introduced. This type of optimality, key-independent optimality, is motivated by applications that assign key values randomly. It is shown that any data structure that is key-independently optimal is expected to execute any access sequence where the key values are assigned arbitrarily to unordered data as fast as any offline binary search tree algorithm, within a multiplicative constant. Asymptotically tight upper and lower bounds are presented for key-independent optimality. Splay trees are shown to be key-independently optimal.
收起
摘要 :
A companion of moving objects is an object group that move together in a period of time. Platoon companions are a generalised companion pattern, which describes a group of objects that move together for time segments, each with so...
展开
A companion of moving objects is an object group that move together in a period of time. Platoon companions are a generalised companion pattern, which describes a group of objects that move together for time segments, each with some minimum consecutive duration of time. This study proposes a method that can instantly discover platoon companions from a special kind of streaming traffic data, called automatic number plate recognition data. Compared to related approaches, the authors transform the companion discovery into a frequent sequence mining problem. The authors propose a data structure, platoon tree (PTree), to record discovered platoon companions. To reduce the cost of tree traversal during mining platoon companions, they utilise the last two together-moving objects of a group to update PTree. Finally, a lot of experiments have been carried out to show the efficiency and effectiveness of the proposed approach.
收起
摘要 :
In front of the large increase of the available amount of structured data (such as XML documents), many algorithms have emerged for dealing with tree-structured data. In this article, we present a probabilistic approach which aims...
展开
In front of the large increase of the available amount of structured data (such as XML documents), many algorithms have emerged for dealing with tree-structured data. In this article, we present a probabilistic approach which aims at a priori pruning noisy or irrelevant subtrees in a set of trees. The originality of this approach, in comparison with classic data reduction techniques, comes from the fact that only a part of a tree (i.e. a subtree) can be deleted, rather than the whole tree itself. Our method is based on the use of confidence intervals, on a partition of subtrees, computed according to a given probability distribution. We propose an original approach to assess these intervals on tree-structured data and we experimentally show its interest in the presence of noise.
收起
摘要 :
Two fault-tree analysis methods to compute the minimal cutsets union probability are: the rare-event approximation, and the minimal cutset upper-bound. The rare-event approximation is accurate if all the basic events have low prob...
展开
Two fault-tree analysis methods to compute the minimal cutsets union probability are: the rare-event approximation, and the minimal cutset upper-bound. The rare-event approximation is accurate if all the basic events have low probabilities. The accuracy improvement provided by the minimal cutset upper-bound approximation is negligible.
收起
摘要 :
Divisible e-cash systems allow users to withdraw a unique coin of value 2n units from a bank, but then to spend it in several times to distinct merchants. In such a system, whereas users want anonymity of their transactions, the b...
展开
Divisible e-cash systems allow users to withdraw a unique coin of value 2n units from a bank, but then to spend it in several times to distinct merchants. In such a system, whereas users want anonymity of their transactions, the bank wants to prevent, or at least detect, double-spending, and trace defrauders. While this primitive was introduced two decades ago, quite a few (really) anonymous constructions have been proposed. In addition, all but one were just proven secure in the random oracle model, but still with either weak security models or quite complex settings and thus costly constructions. The unique proposal, secure in the standard model, appeared recently and is unpractical. As evidence, the authors left the construction of an efficient scheme secure in this model as an open problem. In this study, the authors answer it with the first efficient divisible e-cash system secure in the standard model. It is based on a new way of building the coins, with a unique and public global tree structure for all the coins. Actually, they propose two constructions which offer a tradeoff between efficiency and security. They both achieve constant time for withdrawing and spending amounts of 2ℓ units, while allowing the bank to quickly detect double-spendings by a simple comparison of the serial numbers of deposited coins to the ones of previously spent coins.
收起
摘要 :
A data structure is presented for the storage of graphical information. It is a modified multiple storage quad tree, with four lists in each leaf quad. A substantial improvement is obtained for region queries, in particular on lar...
展开
A data structure is presented for the storage of graphical information. It is a modified multiple storage quad tree, with four lists in each leaf quad. A substantial improvement is obtained for region queries, in particular on large windows, and for tree traversal. On the other hand, only an insignificant increase of memory requirement is noticed in particular situations. The method is not complicated, so it can easily be programmed.
收起
摘要 :
The essence of the modern hashing technique in computer science is the derivation of a number from a nonnumeric key to index into a table where the record containing the key is stored. In this paper, an interestingly similar techn...
展开
The essence of the modern hashing technique in computer science is the derivation of a number from a nonnumeric key to index into a table where the record containing the key is stored. In this paper, an interestingly similar technique used in South Indian musicology in the 18th century is described, and the question of whether it is an anticipation of the hashing technique is briefly addressed. The problem of retrieving a record from a table based upon a given key has been studied extensively. In this paper, I describe one particular approach to this problem-hashing-and also an interesting earlier development very similar to it. It is generally believed that the idea of hashing was originated by H.P. Luhn (1953), and first described in the open literature by A.I. Dumey (1956), but is it possible that the Katapayadi scheme of deriving numbers from names-in conjunction with the applications to which it had been put, especially in classical South Indian musicology-is an early anticipation of the hashing technique? I discuss this issue in detail in this paper.
收起
摘要 :
The concurrent manipulation of an expanded AVI tree (EAVL tree) is considered in this paper. The presented system can support any number of concurrent processes which perform searching, insertion and deletion on the tree. Simulati...
展开
The concurrent manipulation of an expanded AVI tree (EAVL tree) is considered in this paper. The presented system can support any number of concurrent processes which perform searching, insertion and deletion on the tree. Simulation results indicate the high performance of the system. Elaborate techniques are used to achieve such a system unavailable based on any known algorithms. Methods developed in this paper may provide new insights into other problems in the area of concurrent search structure manipulation.
收起
